競プロ典型 90 問 005
(工事中)
解き方
※ ここに書く解き方は、解説に書かれている解き方と異なる この記事においては、数列$ \bm{s} の$ i 番目の要素を$ (\bm{s})_{i} と表記する。ただし、番号は$ 0 から始めるとする。
すなわち、長さ$ n の数列$ \bm{s} の各要素は、先頭から順番に$ (\bm{s})_{0}, (\bm{s})_{1}, \ldots, (\bm{s})_{n-1} のように表記する。
小課題1の解き方を基本として、小課題2や小課題3ではそれを効率化した形になっているため、まずはその基本となる解き方を述べる。
その後に、小課題2や小課題3でどのように効率化したのか、その考え方を述べる。
任意の非負整数$ i について、長さが$ B の非負整数列$ \bm{s}_{i} を次のように定める。
$ 0 以上$ B 未満の$ j について、$ (\bm{s}_{i})_{j} は$ \{ c_{k} \times 10^{i} \mid k \in \mathbb{Z} \land 1 \le k \le K\} の要素で、$ B で割った余りが$ j であるものの個数
また、長さが$ B の非負正数列$ \bm{s} と$ \bm{t} に対し、長さが$ B の非負数列$ \bm{s} \ast \bm{t} を次のように定義する。
$ 0 以上$ B 未満の$ j について、その$ j 番目の要素は$ (\bm{s} \ast \bm{t})_{j} = \sum_{l+l^{\prime} \equiv j \mod B \land 0 \le l \lt B \land 0 \le l^{\prime} \lt B}
$ 0 以上$ B 未満の$ j について、その$ j 番目の要素は$ (\bm{s} \ast \bm{t})_{j} = \sum_{l=0}^{B-1} (\bm{s})_{l} \times (\bm{t})_{(j-l+B) \% B} を満たす。
ただし、$ (j-l+B) \% B は$ (j-l+B) を$ B で割った余りを表すとする。
この演算は結合法則を満たすため、3個以上の数列に対する演算も$ \bm{s} \ast \bm{t} \ast \bm{u} のように括弧を省略して記載する。
このとき、求める答えは$ (\bm{s}_{0} \ast \bm{s}_{1} \ast \cdots \bm{s}_{N-1})_{0}
このとき、求める答えは$ (\bm{s}_{0} \ast \bm{s}_{1} \ast \cdots \ast \bm{s}_{N-1})_{0} (を$ 10^{9}+7 で割った余り)である。
$ N 個の非負数列$ \bm{s}_{0}, \bm{s}_{1}, \ldots ,\bm{s}_{N-1} は、$ 10, 10^{1}, \ldots, 10^{N-1} を$ B で割った余りをそれぞれ求めて、$ c_{1}, c_{2}, \ldots, c_{K} をかければ
$ N 個の非負数列$ \bm{s}_{0}, \bm{s}_{1}, \ldots ,\bm{s}_{N-1} は、愚直に計算して、$ O(N(K+B)) の計算量で計算可能である。
また、$ \bm{s} \ast \bm{t} という演算は、上の定義をそのまま実装すると、一回あたり$ O(B^{2}) の計算量で計算できる。
よって、全体としては$ O(NK+NB^{2}) の計算量で計算できるため、小課題1の制約であれば、これで十分に実行制限時間に間に合う。
以下、この解き方の正当性について述べた後に、小課題2や小課題3に対応するために行った効率化の方法について述べる。
まず、有限個の非負整数からなる集合$ A と$ B を考えて、この2つが下の条件を満たしていると仮定する。
$ \forall a \in A. \forall a^{\prime} \in A. \forall b \in B. \forall b^{\prime} \in B. \left( a+b = a^{\prime}+b^{\prime} \Rightarrow \left( a=a^{\prime} \land b = b^{\prime} \right) \right)
このとき、集合$ C = \{ a+b \in \mathbb{Z} \mid a \in A \land b \in B \} を考える。
また、長さ$ B の非負数列$ \bm{s}_{A} を、$ i 番目の要素$ (\bm{s}_{A})_{i} が$ A の要素のうち$ B で割った余りが$ i であるものの個数となるように定める。
同様に$ \bm{s}_{B} や$ \bm{s}_{C} も定めたとき、上で定めた演算は、$ \bm{s}_{C} = \bm{s}_{A} \ast \bm{s}_{B} となるように定義されている。
例えば、$ a \equiv l \mod B を満たす要素$ a \in A と$ b \equiv j-l \mod B を満たす要素$ b \in B
あー$ B が被ってた…集合の方は$ \mathcal{B} にするとか?いや、いっそ$ X,Y,Z にするか?
私の提出一覧
table: submissions_atcoder_typical90_005
提出のURL 提出時刻 結果 備考